package com.leetcodehot.problems;

import java.util.Arrays;

public class problems746 {
    private int n;
    private int[] memo;

    public int minCostClimbingStairs(int[] cost) {
        this.n = cost.length;
        memo = new int[n + 2];
        Arrays.fill(memo, -1);
        return dfs(n, cost);
    }

    //到达n需要多少cost
    private int dfs(int i, int[] cost) {
        if (i <= 1) return 0;
        if (memo[i] != -1) return memo[i];

        int res = Math.min(dfs(i - 1, cost) + cost[i - 1], dfs(i - 2, cost) + cost[i - 2]);
        memo[i] = res;
        return res;
    }
}
